package org.example.code.test2024.ten_mouth;

import java.util.Scanner;

public class test1013 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入数组大小
        int n = scanner.nextInt();
        int[] arr = new int[n];

        // 输入数组元素
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        boolean flipped = true; // 是否继续翻转标志
        while (flipped) {
            flipped = false; // 假设本轮没有翻转
            for (int i = 0; i < n - 1; i++) {
                int currentSum = arr[i] + arr[i + 1];
                int flippedSum = -arr[i] + -arr[i + 1];

                // 如果翻转可以增加数组和，则进行翻转
                if (flippedSum > currentSum) {
                    arr[i] = -arr[i];
                    arr[i + 1] = -arr[i + 1];
                    flipped = true; // 有翻转，继续下一轮
                }
            }
        }

        // 计算翻转后的最大和
        int maxSum = 0;
        for (int value : arr) {
            maxSum += value;
        }

        // 输出最大和
        System.out.println("最大数组和: " + maxSum);
    }
}
